package com.algorithm.labuladong.ReserverLinkedList;

/**
 * 链表操作
 *
 * @author: tzj
 * @create: 2021-08-09
 **/
public class ReserverLinkedList {

    private static ListNode listNode;

    // 后驱节点
    private static ListNode success = null;

    public static void main(String[] args) {
        traverse(listNode);
//        System.out.println(reverse(listNode));
//        System.out.println(reversePrevN(listNode, 3));
//        System.out.println(reverseBetween(listNode, 2, 4));
    }

    /**
     * 遍历链表中的值
     *
     * @param head
     */
    public static void traverse(ListNode head) {
        if (head==null) return;
        // next不为空，指向下一个
        if (head.next != null) {
            System.out.println(head.next.getVal());
            traverse(head.next);
        }
    }


    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head.next == null) return head;
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }

    /**
     * 反转以 head 为起点的 n 个节点，返回新的头结点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode reversePrevN(ListNode head, int n) {
        if (n == 1) {
            // 记录n+1个节点
            success = head.next;
            return head;
        }

        // 以head.next为起点，需要反转n-1个节点
        ListNode last = reversePrevN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = success;
        return last;
    }

    /**
     * 反转区间中的链表元素
     *
     * @param head
     * @param m
     * @param n
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reversePrevN(head, n);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    static {
        listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = null;
    }

}
